package com.example.arithmeticleetcode.learnArithmetic2.dynamic_programming;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-12-16 11:45
 **/
public class CoinChange {

    public static void main(String[] args) {
        System.out.println(coinChange(19));
        System.out.println(coinChange2(19));
        System.out.println(coinChange3(19));
        System.out.println(coinChange5(19));
        System.out.println("---------------------");
        int n = 41;
        System.out.println(coinChange(n));
        System.out.println(coinChange2(n));
        System.out.println(coinChange3(n));
        System.out.println(coinChange5(n));

        System.out.println("=====================================");

        int[] faces = {1, 5, 20, 25};
        System.out.println(coinChange6(41, faces));
        System.out.println(coinChange6(19, faces));

        System.out.println(Character.isJavaIdentifierStart('t'));


    }

    /**
     * 递推 自底向上 (计算数量+选出哪些硬币)
     *
     * @param n
     * @return
     */
    public static int coinChange6(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i < face) continue;
                int v = dp[i - face];
                if (v >= min || v < 0) continue;
                min = v;
            }
            if (min == Integer.MAX_VALUE) {
                dp[i] = -1;
            } else {
                dp[i] = min + 1;
            }
        }
        return dp[n];
    }

    /**
     * 递推 自底向上 (计算数量+选出哪些硬币)
     *
     * @param n
     * @return
     */
    public static int coinChange5(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        //faces[i]是凑够i分钱最后那枚硬币的面值
        int[] faces = new int[dp.length];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            if (i >= 1 && dp[i - 1] < min) {
                min = dp[i - 1];
                faces[i] = 1;
            }
            if (i >= 5 && dp[i - 5] < min) {
                min = dp[i - 5];
                faces[i] = 5;
            }
            if (i >= 20 && dp[i - 20] < min) {
                min = dp[i - 20];
                faces[i] = 20;
            }
            if (i >= 25 && dp[i - 25] < min) {
                min = dp[i - 25];
                faces[i] = 25;
            }
            dp[i] = min + 1;
        }
        print(faces, n);
        return dp[n];
    }

    private static void print(int[] faces, int n) {
        System.out.print("========    ");
        while (n > 0) {
            System.out.print(faces[n] + "   ");
            n = n - faces[n];
        }
        System.out.println();
    }

    /**
     * 递推 自底向上 (计算数量)
     *
     * @param n
     * @return
     */
    public static int coinChange4(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = dp[i - 1];
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * 递推 自底向上
     *
     * @param n
     * @return
     */
    public static int coinChange3(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = dp[i - 1];
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[n];
    }

    /**
     * 记忆性搜索，自顶向下的调用
     *
     * @param n
     * @return
     */
    public static int coinChange2(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        int[] faces = {1, 5, 20, 15};
        for (int face : faces) {
            if (n < face) break;
            dp[face] = 1;
        }
        return coinChange2(n, dp);
    }

    public static int coinChange2(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            int min1 = Math.min(coinChange2(n - 25, dp), coinChange2(n - 20, dp));
            int min2 = Math.min(coinChange2(n - 5, dp), coinChange2(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
        }
        return dp[n];
    }


    /**
     * 暴力递归  自顶向下的调用，出现了重叠子问题
     *
     * @param money
     * @return
     */
    public static int coinChange(int money) {
        if (money < 1) return Integer.MAX_VALUE;
        if (money == 25 || money == 20 || money == 5 || money == 1) return 1;
        int min1 = Math.min(coinChange(money - 25), coinChange(money - 20));
        int min2 = Math.min(coinChange(money - 5), coinChange(money - 1));
        return Math.min(min1, min2) + 1;
    }

}
